《剑指offer》 24. 反转链表

剑指offer
11 留言

note: 反转链表作为一道简单题，主要考察的是对迭代法和链表数据结构的了解。

题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

1
0 <= 节点个数 <= 5000

方法一 迭代法

思路

首先我们需要一个指向前一个节点的指针pre，然后每次迭代做四件事

  1. 保存当前节点的下个节点
  2. 让当前节点的下一个节点指针改为指向pre指针指向的节点
  3. 让pre指针指向当前节点
  4. 让指向当前节点的指针指向下个节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode * pre = NULL;
        while(head!=NULL){
            ListNode* temp = head->next;
            head->next = pre;
            pre=head;
            head = temp;
        }
        return pre;
    }
};

复杂度分析

  • 时间复杂度$O(n)$。需要遍历每个节点
  • 空间复杂度$O(1)$。只需要一个pre指针，常量级空间。

方法二 递归法

思路

递归的思路其实就是分治，将每部分都要反转的问题，转化为思考现在我有一个节点和它后续已经反转好的节点。思考到这一步就差不多能写出来了。递归终止条件为当前节点的下个节点为空（说明已经是最后一个节点）或者当前节点为空（说明链表为空），此时返回当前节点。

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL || head->next==NULL)
            return head;
        ListNode* cur = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return cur;
    }
};

复杂度分析

  • 时间复杂度$O(n)$。需要遍历每个节点
  • 空间复杂度$O(n)$。递归需要调用栈空间，显然需要链表长度层栈空间。